|
In formal language theory, in particular in algorithmic learning theory, a class ''C'' of languages has finite thickness if every string is contained in at most finitely many languages in ''C''. This condition was introduced by Dana Angluin as a sufficient condition for ''C'' being identifiable in the limit. 〔; here: Condition 3, p.123 mid. Angluin's original requirement (every non-empty string ''set'' be contained in at most finitely many languages) is equivalent.〕 ==The related notion of M-finite thickness== Given a language ''L'' and an indexed class ''C'' = of languages, a member language ''L''''j'' ∈ ''C'' is called a minimal concept of ''L'' within ''C'' if ''L'' ⊆ ''L''''j'', but not ''L'' ⊊ ''L''''i'' ⊆ ''L''''j'' for any ''L''''i'' ∈ ''C''.〔; here: Definition 25〕 The class ''C'' is said to satisfy the MEF-condition if every finite subset ''D'' of a member language ''L''''i'' ∈ ''C'' has a minimal concept ''L''''j'' ⊆ ''L''''i''. Symmetrically, ''C'' is said to satisfy the MFF-condition if every nonempty finite set ''D'' has at most finitely many minimal concepts in ''C''. Finally, ''C'' is said to have M-finite thickness if it satisfies both the MEF- and the MFF-condition. 〔Ambainis et al. 1997, Definition 26〕 Finite thickness implies M-finite thickness.〔Ambainis et al. 1997, Corollary 29〕 However, there are classes that are of M-finite thickness but not of finite thickness (for example, any class of languages ''C'' = such that ''L''1 ⊆ ''L''2 ⊆ ''L''3 ⊆ ...). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Finite thickness」の詳細全文を読む スポンサード リンク
|